package 回溯;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.List;

/**
 * @author admin
 * @version 1.0.0
 * @ClassName 分割回文字符串.java
 * @Description TODO
 * @createTime 2020年11月02日 22:42:00
 *
 *
 * 就是子集这题的的变形 多了一个回文判断而已
 */
public class 分割回文字符串 {

    public class Solution {
        List<List<String>> res = new ArrayList<>();
        public List<List<String>> partition(String s) {
            int len = s.length();

            if (len == 0) {
                return res;
            }
            Deque<String> stack = new ArrayDeque<>();
            backtracking(s, 0, len, stack);
            return res;
        }

        private void backtracking(String s, int start, int len, Deque<String> path) {
            if (start == len) {
                res.add(new ArrayList<>(path));
                return;
            }

            for (int i = start; i < len; i++) {


                if (!checkPalindrome(s, start, i)) {
                    continue;
                }

                path.addLast(s.substring(start, i + 1));
                backtracking(s, i + 1, len, path);
                path.removeLast();
            }
        }

        private boolean checkPalindrome(String str, int left, int right) {
            // 严格小于即可
            while (left < right) {
                if (str.charAt(left) != str.charAt(right)) {
                    return false;
                }
                left++;
                right--;
            }
            return true;
        }
    }

}
